package _interview150;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 68. 文本左右对齐
 */
public class No68 {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        Queue<String> path = new LinkedList<>();
        int curSurplus = maxWidth, curLen = 0;
        for (String word : words) {
            if (word.length() > curSurplus) {
                StringBuilder sb = new StringBuilder();
                int emptyLen = maxWidth - curLen;
                int wordCount = path.size();
                if (wordCount == 1) {
                    sb.append(path.poll());
                    sb.append(" ".repeat(emptyLen));
                } else if (wordCount > 1) {
                    int len = emptyLen / (wordCount - 1);
                    int surplus = emptyLen % (wordCount - 1);
                    for (int j = 0; j < wordCount - 1; j++) {
                        sb.append(path.poll());
                        sb.append(" ".repeat(Math.max(0, --surplus >= 0 ? len + 1 : len)));
                    }
                    sb.append(path.poll());
                }
                ans.add(sb.toString());
                curSurplus = maxWidth;
                curLen = 0;
            }
            if (word.length() <= curSurplus) {
                path.offer(word);
                curSurplus -= word.length() + 1;
                curLen += word.length();
            }
        }


        StringBuilder sb = new StringBuilder();
        int emptyLen = maxWidth - curLen;
        int wordCount = path.size();
        for (int j = 0; j < wordCount - 1; j++) {
            sb.append(path.poll());
            sb.append(" ".repeat(1));
        }
        sb.append(path.poll());
        sb.append(" ".repeat(emptyLen - wordCount + 1));
        ans.add(sb.toString());
        return ans;
    }
}
